#include <vector>

class disjoint_set {
    private:
        std::vector<int> fa, size;
    
    public:
        disjoint_set(const size_t &n) {
            fa.resize(n + 1);
            size.resize(n + 1);
            for (size_t i = 0; i <= n; i++) {
                fa[i] = i;
                size[i] = 1;
            }
        }

        int query(int x);
        bool merge(int x, int y);
};

inline int disjoint_set::query(int x) {
    return x == fa[x] ? x : fa[x] = query(fa[x]);
}

bool disjoint_set::merge(int x, int y) {
    int xx = query(x), yy = query(y);
    if (xx == yy) return 0;
    if (size[xx] > size[yy]) std::swap(xx, yy);
    fa[xx] = yy;
    size[yy] += size[xx];
    return 1;
}
